/**
//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 8 
// -10 <= nums[i] <= 10 
// 
// Related Topics 数组 回溯 👍 1024 👎 0

*/

package com.xixi.basicAlgroithms.backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ID00047PermutationsIi {
public static void main(String[] args) {
Solution solution = new ID00047PermutationsIi().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        backTracking(nums,nums.length, 0, new ArrayList<>(), new boolean[nums.length], new HashSet<>(nums.length));
        return result;
    }

    /*
     * @Desc:
     * @Author vincentML
     * @Date: 2022/4/16 23:13
     * @param nums 原数组
     * @param nLength 原数组长度
     * @param index 当前添加到多少个数字，从0开始
     * @param path 路径
     * @param usedSet 记录如果本层有重复数字已经用过了，那就不用再递归了下去了,直接下个数字
    */
    public void backTracking(int[] nums, int nLength, int index, List<Integer> path, boolean[] used, Set<Integer> usedSet){

        if(index == nLength){
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nLength; ++i ){
            if(used[i]) continue; //上一层用过了，直接跳
            if(usedSet.contains(nums[i])) continue; //如果本层碰到重复的数字，跳过，本层已经有过递归了。

            path.add(nums[i]);
            used[i] = true;
            usedSet.add(nums[i]);
            backTracking(nums, nLength, index +1, path, used, new HashSet<>(nums.length));

            path.remove(path.size() -1);
            used[i] = false;


        }



    }
}
//leetcode submit region end(Prohibit modification and deletion)




}